/*
  互质树
  题目描述
    给定一个 n 个结点的树，结点编号从 1 到 n，每个结点有一个权值 ai，树的根结点为 1 号结点。
    对树中任意结点 u，从结点 u 到根的最短路径上的点都是结点 u 的祖先结点。
    本问题中认为：一个结点不是它自己的祖先结点。
    对所有结点 1 ≤ i ≤ n，求 ansi：
      离结点 i 最近的祖先结点编号，且满足 ai 和 aansi 互质，若不存在这样的结点，则 ansi = −1。
  输入描述
    第 1 行，两个正整数 n。
    第 2 行，n 个正整数 ai，表示结点 i 的权值。
    接下来 n−1 行，第 i (1 ≤ i ≤ n) 行两个整数 u, v，表示树中的一条边。
  输出描述
    一行，n 个整数，表示答案。
  样例1
    输入
      4
      2 3 3 2
      1 2
      2 3
      2 4
    输出
      -1 1 1 2
  样例2
    输入
      7
      5 6 10 2 3 6 15
      1 2
      1 3
      2 4
      2 5
      3 6
      3 7
    输出
      -1 1 -1 1 1 1 -1
  提示
    1 ≤ n ≤ 10^5,
    1 ≤ u, v ≤ n,
    1 ≤ ai ≤ 50
*/